package com.leetcode.LC_MED;

import java.util.HashSet;

public class LC287 {
    public int findDuplicate(int[] nums) {

        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            } else {
                set.add(num);
            }
        }
        return -1;
    }

    //https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-kuai-man-zhi-zhen-by-jie-fang-qu-de-tian/
    public int findDuplicate2(int[] nums) {
        int fast = 0, slow = 0;
        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (slow == fast) {
                fast = 0;
                while (nums[slow] != nums[fast]) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }
}
